package star.基础.快速排序;

import star.Utils;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {5,7,2,8,1,9,5,6};
        quickSort(arr,0,7);
        Utils.traversal(arr);
    }

    private static void quickSort(int[] arr,int L,int R) {
        if(L < R){
            Utils.swap(arr,L+(int)(Math.random()*(R-L+1)),R);
            int[] p = partition(arr,L,R);
            quickSort(arr,L,p[0]);
            quickSort(arr,p[1],R);
        }
    }

    private static int[] partition(int[] arr, int L, int R) {
        int left = L-1;
        int right = R;
        while (L < right){
            if (arr[L] > arr[R]){
                Utils.swap(arr,L,--right);
            }else if (arr[L] < arr[R]){
                Utils.swap(arr,L++,++left);
            }else {
                L++;
            }
        }
        Utils.swap(arr,R,right);
        return new int[]{left,right+1};
    }
}
